#!/usr/bin/env python3

class Node:
    def __init__(self, keyandvalue, left=None, right=None):
        self.left = None
        self.key = keyandvalue[0]
        self.data = keyandvalue[1]
        self.right = None

    def preorder(self):
        print(self.data, end=' ')
        if self.left is not None:
            self.left.preorder()

        if self.right is not None:
            self.right.preorder()


class BinarySearchTree:
    def __init__(self, rootnode=None):
        self.root = rootnode

    def insert(self, key, value):
        node = Node((key, value))
        if self.root is None:
            self.root = node
            return
        
        current = self.root
        while True:
            if current.key > key:
                if current.left is None:
                    current.left = node
                    break
                current = current.left
            elif current.key < key:
                if current.right is None:
                    current.right = node
                    break
                current = current.right
            else:
                raise Error("Not support two node has same key")

    def delete(self, key):
        last = None
        current = self.root
        while current is not None:
            if current.key == key:
                alternative_node = BinarySearchTree._find_alternative_node(current)
                if last is None:
                    self.root = alternative_node
                elif last.key > key:
                    last.left = alternative_node
                else:
                    last.right = alternative_node
                break
            elif current.key > key:
                last = current
                current = current.left
            else:
                last = current
                current = current.right

    def preorder(self):
        if self.root is not None:
            self.root.preorder()
            print()
        else:
            print("BinarySearchTree is Empty.")

    @staticmethod
    def _find_alternative_node(node):
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        result_node = node.right
        right_tree_leftest_node = result_node
        while True:
            if right_tree_leftest_node.left is None:
                break
            right_tree_leftest_node = right_tree_leftest_node.left
        right_tree_leftest_node.left = node.left
        return result_node
            
            

    def search(self, key):
        if self.root is None:
            return None
        current = self.root
        while True:
            if current.key == key:
                return current.data
            if current.key > key:
                if current.left is None:
                    return None
                current = current.left
            else:
                if current.right is None:
                    return None
                current = current.right


#                5
#              /   \
#             3     6
#           /  \     \
#          1    4     8    
#                    /
#                   7
if __name__ == '__main__':
    tree = BinarySearchTree()
    tree.insert(5, '5')
    tree.insert(3, '3')
    tree.insert(6, '6')
    tree.insert(1, '1')
    tree.insert(4, '4')
    tree.insert(8, '8')
    tree.insert(7, '7')
    tree.preorder()

    assert tree.search(7) == '7'
    tree.delete(3)
    tree.preorder()
    tree.insert(3, 'b3')
    tree.delete(5)
    tree.preorder()
